
package com.offer.leetcode;

import java.util.Arrays;

/**
 * Solution40
 */
public class Solution40WithHeap {

    public static void main(final String[] args) {
        Solution40WithHeap s = new Solution40WithHeap();
        final int[] nums = { 3,2,1 };

        // final int[] result = s.getLeastNumbers(nums, 8);
        final int[] result = s.getLeastNumbers(nums, 2);

        Arrays.stream(result).forEach(System.out::println);
    }

    /**
     * 获取topK数据
     * @param nums
     * @param k
     * @return
     */
    public int[] getLeastNumbers(final int[] nums, final int k) {

        if (nums == null) {
            return nums;
        }

        if (k <= 0) {
            return new int[0];
        }

        // 1. 直接采用nums构建堆, 注意数组从第0个开始
        for (int i = nums.length / 2 - 1; i >= 0; --i) {
            // 自上而下构建小顶堆
            this.heapfy(nums, nums.length, i);
        }

        // 2. 删除堆顶元素，并将最后一个元素放在堆顶，重新堆化

        int[] result = new int[k];

        for (int i = 0; i < k; ++i) {
            result[i] = this.removeTop(nums, nums.length - 1 - i);
        }

        return result;

    }

    /**
     * 
     * @param nums
     * @return
     */
    private final int removeTop(int[] nums, int length) {
        int ret = nums[0];
        nums[0] = nums[length];

        this.heapfy(nums, length - 1, 0);

        return ret;

    }

    /**
     * 
     * @param nums   ： 数组
     * @param length : 数组的长度
     * @param start  : 父节点
     */
    private final void heapfy(int[] nums, int length, int start) {

        int cur = start;
        while (true) {
            int minIndex = cur;
            // 1. 寻找最小子节点位置
            int left = 2 * cur + 1;
            if (left <= length && nums[left] < nums[minIndex]) {
                minIndex = left;
            }
            int right = 2 * cur + 2;
            if (right < length && nums[right] < nums[minIndex]) {
                minIndex = right;
            }

            if (minIndex == cur) {
                break;
            }

            this.swap(nums, minIndex, cur);

            cur = minIndex;

        }
    }

    /**
     * 
     * @param nums
     * @param a
     * @param b
     */
    private final void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }

}